class Solution {
    public int numSquares(int n) {
        int INF = 0x3f3f3f3f;
        int[] dp = new int[n + 1];
        for(int j = 1; j <= n; j++) dp[j] = INF;
        for(int i = 1; i <= Math.sqrt(n); i++){
            for(int j = i * i; j <= n; j++){
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
}